Algorithmique - NSI

Recherche dichotomique

Exercice 1 : Recherche dichotomique, compléter les étapes

On considère la liste triée [1, 10, 13, 20, 26, 36, 42, 53, 59, 74, 88].

On recherche par dichotomie la valeur 26 dans cette liste.
Compléter les étapes de cette recherche :

Pour la première itération, on recherche sur les éléments de rang à .

Pour la deuxième itération, on recherche sur les éléments de rang à .

Pour la troisième itération, on recherche sur les éléments de rang à .

Pour la quatrième itération, on compare l'élément de rang à la valeur recherchée.

Exercice 2 : Recherche dichotomique, déterminer le nombre d'itérations

On considère la liste triée [7, 9, 11, 42, 54, 60, 77, 81, 82, 88].
Combien d'itérations vont être nécessaires pour trouver la valeur 9 dans cette liste en utilisant une recherche dichotomique ?

Exercice 3 : Recherche dichotomique, compléter les étapes

On considère la liste triée [13, 22, 27, 39, 46, 54, 55, 60, 81].

On recherche par dichotomie la valeur 27 dans cette liste.
Compléter les étapes de cette recherche :

Pour la première itération, on recherche sur les éléments de rang à .

Pour la deuxième itération, on recherche sur les éléments de rang à .

Pour la troisième itération, on recherche sur les éléments de rang à .

Exercice 4 : Recherche dichotomique, déterminer le nombre d'itérations

On considère la liste triée [2, 3, 4, 23, 31, 40, 51, 53, 61, 65, 70, 85].
Combien d'itérations vont être nécessaires pour trouver la valeur 23 dans cette liste en utilisant une recherche dichotomique ?

Exercice 5 : Recherche dichotomique, compléter les étapes

On considère la liste triée [20, 29, 40, 47, 48, 88, 92, 98].

On recherche par dichotomie la valeur 47 dans cette liste.
Compléter les étapes de cette recherche :

Pour la première itération, on recherche sur les éléments de rang à .

Revenir au choix du niveau